package 牛客面试;

public class 旋转数组的最小元素 {

    /**
     * 题目描述
     * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
     * 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
     * NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
     *
     * 示例1
     * 输入
     * [3,4,5,1,2]
     * 返回值
     * 1
     */

    public int minNumberInRotateArray(int [] array) {
        return dg(array,0,array.length-1);
    }

    private int dg(int[] array,int left,int right){

        //终止条件
        if(left+1==right){
            return array[left]>array[right]?array[right]:array[left];
        }

        int minNumber=(right-left)/2+left;
        int mid=array[minNumber];//中间值

        if(array[left]>mid){
            //最小值在左~中
            return dg(array,left,minNumber);
        }else{
            //最小值在中~右
            return dg(array,minNumber,right);
        }

    }

    public static void main(String[] args) {
        旋转数组的最小元素 n =new 旋转数组的最小元素();
        int result = n.minNumberInRotateArray(new int[]{3, 4, 5, 1, 2});
        System.out.println(result);
    }

}
